/**
 * Project Name:JavaBaseReview
 * Package Name:com.xuwei.base.tree
 * author:David
 * Date:2016年5月8日下午3:56:10
 * Copyright (c) 2016, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.tree;

import com.xuwei.base.link.Node;

/**
 * 二叉树存储结构的结点定义（采用三叉链表）
 * @author David
 * @since 2016年5月8日 下午3:56:10
 * @version 
 * @since JDK 1.6
 */
public class BinTreeNode implements Node {
	private Object data;//数据域
	private BinTreeNode parent;//父结点
	private BinTreeNode lChild;//左子结点
	private BinTreeNode rChild;//右子结点
	private int height; //以该结点为根的子树的高度
	private int size;   //该结点子孙数（包括当前结点）
	
	
	/**
	 * 
	 */
	public BinTreeNode() {
		this(null);
	}
	
	public BinTreeNode(Object e){
		data = e;
//		height = e==null?0:1;
		height = 0;
		size = 1;
		parent = lChild = rChild = null;
	}
	
	@Override
	public Object getData() {
		return data;
	}

	@Override
	public void setData(Object obj) {
		data = obj;
	}
	
	/****辅助方法，判断当前结点位置情况看*********/
	//判断是否有父亲
	public boolean hasParent(){
		return parent!=null;
	}
	//判断是否有左子树
	public boolean hasLChild(){
		return lChild!=null;
	}
	//判断是否有右子树
	public boolean hasRChild(){
		return rChild!=null;
	}
	//判断是否为叶子结点
	public boolean isLeaf(){
		return !hasLChild()&&!hasRChild();
	}
	//判断是否为某结点的左子树
	public boolean isLChild(){
		return hasParent()&&this==parent.lChild;
	}
	//判断是否为某结点的右子树
	public boolean isRChild(){
		return hasParent()&&this==parent.rChild;
	}
	
	/*****与height相关的方法********/
	//取结点的高度，即以该结点为根的树的高度
	public int getHeight(){
		return height;
	}
	//更新当前结点及其祖先的高度
	public void updateHeight(){
		int newH = 0;//新高度初始化为0，高度等于左右子树高度加1中的大者
		if(hasLChild()){
			newH = Math.max(newH, 1+getLChild().getHeight());
		}
		if(hasRChild()){
			newH = Math.max(newH, 1+getRChild().getHeight());
		}
		if(newH == height){
			return;//高度没有发生变化则直接返回
		}
		height = newH;//否则更新高度
		if(hasParent()){
			getParent().updateHeight();//递归更新祖先的高度
		}
	}
	
	/*****与size相关的方法********/
	//取以该结点为根的树的结点数
	public int getSize(){
		return size;
	}
	//更新当前结点及其祖先的子孙数
	public void updateSize(){
		size = 1;//初始化为1，结点本身
		if(hasLChild()){
			size+=getLChild().getSize();//加上左子树规模
		}
		if(hasRChild()){
			size+=getRChild().getSize();//加上右子树规模
		}
		if(hasParent()){
			getParent().updateSize();//递归更新祖先的规模
		}
	}
	
	/*******与parent相关的方法*************/
	public BinTreeNode getParent() {
		return parent;
	}
	//断开与父亲的关系
	public void sever(){
		if(!hasParent()){
			return;
		}
		if(isLChild()){
			parent.lChild = null;
		}else{
			parent.rChild = null;
		}
		parent.updateHeight();//更新父结点及其祖先高度
		parent.updateSize();  //更新父结点及其祖先规模
		parent = null;
	}
	
	/*****与lChild相关的方法***********/
	//取左孩子
	public BinTreeNode getLChild() {
		return lChild;
	}

	//设置当前结点的左子树，返回原左子树
	public BinTreeNode setLChild(BinTreeNode lc) {
		BinTreeNode oldLC = this.lChild;
		if(hasLChild()){
			lChild.sever();//断开当前左子树与结点的关系
		}
		if(lc!=null){
			lc.sever();//断开lc与其父结点的关系
			this.lChild = lc;//确定父子关系
			lc.parent = this;
			this.updateHeight();
			this.updateSize();
		}
		return oldLC;
	}
	
	/******与rChild相关的方法****************/
	//取右右子树
	public BinTreeNode getRChild() {
		return rChild;
	}

	//设置当前结点的右子树，返回原右子树
	public BinTreeNode setRChild(BinTreeNode rc) {
		BinTreeNode oldRC = this.rChild;
		if(hasRChild()){
			rChild.sever();//断开当前右子树与结点的关系
		}
		if(rc!=null){
			rc.sever();//断开rc与其父结点的关系
			this.rChild = rc;
			rc.parent = this;
			this.updateHeight();//更新当前结点及其祖先高度
			this.updateSize();//更新当前结点及其祖先规模
		}
		return oldRC; //返回原右子树
	}

	public void setHeight(int height) {
		this.height = height;
	}


}
